/*
 * sortedArrayToBST.cpp
 *
 *  Created on: Jul 19, 2012
 *      Author: jh238d
 */

#include "BSTNode.h"
#include <iostream>
#include <climits>
#include "LinkedListNode.h"
using namespace std;

BSTNode* sorted_array_to_balanced_BST(int a[], int l, int r){
	if(l>r) return NULL;
	int m=l+(r-l)/2;
	BSTNode *node = new BSTNode();
	node->data=a[m];
	node->left = sorted_array_to_balanced_BST(a, l, m-1);
	node->right = sorted_array_to_balanced_BST(a, m+1, r);
	return node;

}

BSTNode* sorted_list_to_balanced_BST(Node *&head, int l, int r){
	if(!head||l>r) return NULL;
	int m = l+(r-l)/2;
	BSTNode *root = new BSTNode();
	root->left = sorted_list_to_balanced_BST(head, l, m-1);
	root->data = head->data;
	root->right = sorted_list_to_balanced_BST(head->next, m+1, r);
	return root;
}


